Search Results

Documents authored by Fleischer, Rudolf

Document
DOI: 10.4230/LIPIcs.FUN.2016.17
Counting Circles Without Computing Them

Authors: Rudolf Fleischer

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract
In this paper we engineer a fast algorithm to count the number of triangles defined by three lines out of a set of n lines whose circumcircle contains the origin. The trick is not to compute any triangles or circles.
Cite as

Rudolf Fleischer. Counting Circles Without Computing Them. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 17:1-17:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fleischer:LIPIcs.FUN.2016.17,
  author =	{Fleischer, Rudolf},
  title =	{{Counting Circles Without Computing Them}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{17:1--17:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.17},
  URN =		{urn:nbn:de:0030-drops-58767},
  doi =		{10.4230/LIPIcs.FUN.2016.17},
  annote =	{Keywords: lines arrangement, triangle, circumcircle, inscribed angle theorem}
}
Document
DOI: 10.4230/DagSemProc.06421.1
06421 Abstracts Collection – Robot Navigation

Authors: Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract
From 15.10.06 to 20.10.06, the Dagstuhl Seminar 06421 ``Robot Navigation''generate automatically was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz. 06421 Abstracts Collection – Robot Navigation. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06421.1,
  author =	{Fekete, S\'{a}ndor and Fleischer, Rudolf and Klein, Rolf and Lopez-Ortiz, Alejandro},
  title =	{{06421 Abstracts Collection – Robot Navigation}},
  booktitle =	{Robot Navigation},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.1},
  URN =		{urn:nbn:de:0030-drops-8890},
  doi =		{10.4230/DagSemProc.06421.1},
  annote =	{Keywords: Motion planning, robotics, computational geometry, online algorithms}
}
Document
DOI: 10.4230/DagSemProc.06421.2
06421 Executive Summary – Robot Navigation

Authors: Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract
For quite a number of years, researchers from various fields have studied problems motivated by Robot Navigation. People in Online Algorithms have developed strategies that can deal with the inherent lack of information an autonomous robot encounters, as it sets out to perform a task in an unknown environment. Computational Geometers have obtained many results on the efficient planning of collision-free motions, and on visibility problems. Scientists and engineers in Robotics have perfected real robots to an astounding degree. Economic household robots and artificial pets are now available; more complex robots are able to carry out difficult search-and-rescue and exploration missions. The goal of this seminar is to bring together researchers from robotics, computational geometry, and online algorithms, in order to exchange problems and ideas, and to jointly work towards solutions. The following questions seem crucial. Given the advanced level of technical development, what are the strategic planning problems researchers in robotics need to solve in the next decade? How can real environments and robots be modeled, so that planning problems become tractable by algorithmic methods, and solutions are still significant for applications? In particular, what can be assumed about perception and motion accuracy? We are planning for plenary sessions where members of all groups can present their problems and recent work. In addition, there will be plenty of time for discussions.
Cite as

Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz. 06421 Executive Summary – Robot Navigation. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06421.2,
  author =	{Fekete, S\'{a}ndor and Fleischer, Rudolf and Klein, Rolf and Lopez-Ortiz, Alejandro},
  title =	{{06421 Executive Summary – Robot Navigation}},
  booktitle =	{Robot Navigation},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.2},
  URN =		{urn:nbn:de:0030-drops-8720},
  doi =		{10.4230/DagSemProc.06421.2},
  annote =	{Keywords: Motion planning, robotics, computational geometry, online algorithms}
}
Document
DOI: 10.4230/DagSemProc.06421.5
Competitive Online Searching for a Ray in the Plane

Authors: Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract
We consider the problem of a searcher that looks, for example, for a lost flashlight in a dusty environment. The searcher finds the flashlight as soon as it crosses the ray emanating from the flashlight. In order to pick it up, the searcher moves to the origin of the light beam. We compare the length of the path of the searcher to the shortest path to the goal. First, we give a search strategy for a special case of the ray search---the window shopper problem---, where the ray we are looking for is perpendicular to a known ray. Our strategy achieves a competitive factor of $1.059ldots$, which is optimal. Then, we consider rays in arbitrary position in the plane. We present an online strategy that achieves a factor of $22.513ldots$, and give a lower bound of $2pi,e=17.079ldots$.
Cite as

Andrea Eubeler, Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen. Competitive Online Searching for a Ray in the Plane. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{eubeler_et_al:DagSemProc.06421.5,
  author =	{Eubeler, Andrea and Fleischer, Rudolf and Kamphans, Tom and Klein, Rolf and Langetepe, Elmar and Trippen, Gerhard},
  title =	{{Competitive Online Searching for a Ray in the Plane}},
  booktitle =	{Robot Navigation},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.5},
  URN =		{urn:nbn:de:0030-drops-8687},
  doi =		{10.4230/DagSemProc.06421.5},
  annote =	{Keywords: Online motion planning, competitive analysis, ray search}
}
Document
DOI: 10.4230/DagSemProc.06091.3
Die Another Day

Authors: Rudolf Fleischer

Published in: Dagstuhl Seminar Proceedings, Volume 6091, Data Structures (2006)

Abstract
The hydra was a many-headed monster from Greek mythology that could grow one or two new heads when one of its heads got cut off. It was the second task of Hercules to kill this monster. In an abstract sense a hydra can be modeled by a tree where the leaves are the heads, and when a head is cut off some subtrees get duplicated. Different hydra species differ by the location of subtrees to be duplicated and by the number of new subtrees grown in each step. Using some deep mathematics, it had been shown that two classes of rather restricted hydra species must always die, independent of the order in which heads are cut off. In this paper we provide an elementary proof which actually gives a complete classification of all hydra species as immortal or doomed. Now, if Hercules had known this...
Cite as

Rudolf Fleischer. Die Another Day. In Data Structures. Dagstuhl Seminar Proceedings, Volume 6091, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{fleischer:DagSemProc.06091.3,
  author =	{Fleischer, Rudolf},
  title =	{{Die Another Day}},
  booktitle =	{Data Structures},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6091},
  editor =	{Lars Arge and Robert Sedgewick and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06091.3},
  URN =		{urn:nbn:de:0030-drops-7652},
  doi =		{10.4230/DagSemProc.06091.3},
  annote =	{Keywords: Hydra, Koenig's Lemma, Peano Arithmetic}
}
Document
DOI: 10.4230/DagSemRep.406
Robot Navigation (Dagstuhl Seminar 03501)

Authors: Rudolf Fleischer and Rolf Klein

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Rudolf Fleischer and Rolf Klein. Robot Navigation (Dagstuhl Seminar 03501). Dagstuhl Seminar Report 406, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{fleischer_et_al:DagSemRep.406,
  author =	{Fleischer, Rudolf and Klein, Rolf},
  title =	{{Robot Navigation (Dagstuhl Seminar 03501)}},
  pages =	{1--4},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{406},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.406},
  URN =		{urn:nbn:de:0030-drops-152863},
  doi =		{10.4230/DagSemRep.406},
}
Document
DOI: 10.4230/DagSemRep.353
Experimental Algorithmics (Dagstuhl Seminar 02371)

Authors: Jon Louis Bentley, Rudolf Fleischer, Bernard Moret, and Erik Meineche Schmidt

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Jon Louis Bentley, Rudolf Fleischer, Bernard Moret, and Erik Meineche Schmidt. Experimental Algorithmics (Dagstuhl Seminar 02371). Dagstuhl Seminar Report 353, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{bentley_et_al:DagSemRep.353,
  author =	{Bentley, Jon Louis and Fleischer, Rudolf and Moret, Bernard and Schmidt, Erik Meineche},
  title =	{{Experimental Algorithmics (Dagstuhl Seminar 02371)}},
  pages =	{1--25},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{353},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.353},
  URN =		{urn:nbn:de:0030-drops-152339},
  doi =		{10.4230/DagSemRep.353},
}
Document
DOI: 10.4230/DagSemRep.334
Algorithmic Combinatorial Game Theory (Dagstuhl Seminar 02081)

Authors: Erik D. Demaine, Rudolf Fleischer, Avierzi Fraenkel, and Richard Nowakowski

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Erik D. Demaine, Rudolf Fleischer, Avierzi Fraenkel, and Richard Nowakowski. Algorithmic Combinatorial Game Theory (Dagstuhl Seminar 02081). Dagstuhl Seminar Report 334, pp. 1-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{demaine_et_al:DagSemRep.334,
  author =	{Demaine, Erik D. and Fleischer, Rudolf and Fraenkel, Avierzi and Nowakowski, Richard},
  title =	{{Algorithmic Combinatorial Game Theory (Dagstuhl Seminar 02081)}},
  pages =	{1--39},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{334},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.334},
  URN =		{urn:nbn:de:0030-drops-152169},
  doi =		{10.4230/DagSemRep.334},
}
Document
DOI: 10.4230/DagSemRep.285
Experimental Algorithmics (Dagstuhl Seminar 00371)

Authors: Rudolf Fleischer, Bernard Moret, and Erik Meineche Schmidt

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Rudolf Fleischer, Bernard Moret, and Erik Meineche Schmidt. Experimental Algorithmics (Dagstuhl Seminar 00371). Dagstuhl Seminar Report 285, pp. 1-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2001)

Copy BibTex To Clipboard

@TechReport{fleischer_et_al:DagSemRep.285,
  author =	{Fleischer, Rudolf and Moret, Bernard and Meineche Schmidt, Erik},
  title =	{{Experimental Algorithmics (Dagstuhl Seminar 00371)}},
  pages =	{1--38},
  ISSN =	{1619-0203},
  year =	{2001},
  type = 	{Dagstuhl Seminar Report},
  number =	{285},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.285},
  URN =		{urn:nbn:de:0030-drops-151691},
  doi =		{10.4230/DagSemRep.285},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact